#Lưu ý: Tải lại trang nếu bạn thấy các ký hiệu toán học quá nhỏ.
Mục lục
1. Tóm tắt đề bài
Marisa có \(n\) tấm ván, tấm ván thứ \(i\) có thể che từ vị trí \(x_i\) đến vị trí \(y_i\) của mái nhà có kích thước \(L\).
Có \(q\) ngày mưa, vào ngày mưa thứ \(i\) thì mái nhà dột từ vị trí \(l_i\) đến vị trí \(r_i\). Với mỗi ngày bạn hãy giúp Marisa xác định số lượng ít nhất tấm ván cần dùng để che mái nhà hoặc in ra \(-1\) nếu không thể che hết được. Lưu ý rằng có thể chồng các tấm ván lên nhau và vào cuối ngày Marisa sẽ gỡ hết những tấm ván đã dùng để dùng tiếp vào ngày hôm sau.
Giới hạn:
- \(1 \leq n,q,L \leq 10^5 \).
- \(1 \leq x_i \leq y_i \leq L, \) với \( 1 \leq i \leq n \).
- \(1 \leq l_i \leq r_i \leq L, \) với \( 1 \leq i \leq q \).
2. Lời giải
a. Ý tưởng chính
Giả sử ta đang cần phủ đoạn \([l..r]\), hãy hình dung chúng ta bắt đầu tại vị trí \(r\) và sẽ dùng một số tấm ván để di chuyển đến vị trí \(l\). Vì cần phải cực tiểu số tấm ván nên chúng ta sẽ chọn tấm ván sao cho nó có thể giúp chúng ta di chuyển ra xa nhất tính từ vị trí đang đứng.
Từ cách hình dung trên ta có ý tưởng cho một thuật toán tham lam như sau:
Tính trước mảng \(f[x]\) theo định nghĩa: \(f[x] = y \) sao cho tồn tại một tấm ván phủ được hết đoạn \([y + 1..x] \) và \(y\) là nhỏ nhất, nếu không tồn tại vị trí \(y\) thỏa mãn thì \(f[x] = 0 \). Để tính mảng này trong thời gian cho phép thì có nhiều cách chẳng hạn như sử dụng kỹ thuật Sweep Line, dùng CTDL để truy vấn max/min, ...
Giả sử đang cần phủ đoạn \([l..r]\), sử dụng ý tưởng giống cách hình dung trên, ta cũng bắt đầu tại \(r\). Đặt \(j = f[r] \) nếu \(j \geq l \) thì ta sẽ di chuyển tới vị trí \(j\) và tăng biến \(\texttt{ans} \) lên \(1\) (ban đầu \(\texttt{ans} = 0\)).
Lặp lại các thao tác trên cho tới khi không thể di chuyển tiếp được nữa (tức \(j < l\)) thì ta có hai trường hợp có thể xảy ra như sau:
- Tồn tại một tấm ván bắt đầu tại vị trí \(j + 1\): khi đó đáp án của chúng ta là \(\texttt{ans} + 1 \).
- Ngược lại: đáp án của chúng ta là \(-1\) do không thể phủ được hết đoạn \([l..r] \).
Sở dĩ chúng ta cần xét hai trường hợp trên là vì mỗi lần di chuyển từ vị trí \(i\) đến vị trí \(j\) thì đồng nghĩa với việc chúng ta đã đặt một tấm ván phủ đoạn \([j + 1..i]\), điều này dẫn đến việc kể cả sau một vài thao tác và chúng ta kết thúc ở vị trí \(l\) thì chúng ta vẫn chưa thực sự phủ được hết đoạn \([l..r] \). Do đó ta mới cần phải xét riêng trường hợp này để đặt tấm ván cuối cùng.
b. Cải tiến thuật toán
Với cách làm ở trên thì ta đã có một thuật toán với độ phức tạp thời gian cho mỗi truy vấn là \(O(n) \), tổng quát lại là \(O(n \cdot q) \) không tính chi phí tính mảng \(f\). Rõ ràng là không khả thi với giới hạn của đề bài đưa ra.
Chìa khóa để chúng ta tăng tốc thuật toán đó là thông qua một nhận xét quan trọng như sau:
Nếu coi mảng \(f\) như là một hàm số thì \(\texttt{ans} + 1 \) của chúng ta chính là số lần lặp hàm \(f(r) \), tổng quát hơn, giả sử luôn tồn tại ít nhất một cách để phủ hết đoạn \([1..r] \) thì sau \(k\) lần lặp hàm \(f(r)\):
$$f \underbrace{(f(f(\dots f(r))))}_k$$
Chúng ta đã tới được vị trí \(i\) sao cho toàn bộ đoạn \([i + 1..r] \) đều đã được phủ ít nhất một tấm ván.
\(\Rightarrow \) Nếu chúng ta lặp hàm này \(\texttt{ans} + 1 \) lần thì chắc chắn đã phủ được hết đoạn \([l..r] \).
Tới đây thuật toán của chúng ta đã có thể tăng tốc bằng kỹ thuật Binary Lifting. Ta định nghĩa lại mảng \(f\) như sau:
Gọi \(f[j][x] =\) vị trí sẽ tới sau khi lặp hàm \(f(x)\) \(2^j\) lần. Như vậy \(f[j][x] \) sẽ được tính bằng công thức:
$$ f[j][x] = \begin{cases} y, & j = 0 \\ f[j - 1][f[j - 1][x]], & j > 0 \\ \end{cases} $$
Khi \(j = 0\) thì \(f[0][x]\) trở thành mảng \(f[x]\) mà ta đã định nghĩa trước đó.
Để tính đáp án ta chỉ cần "nhảy" trên mảng \(f\) và xét các trường hợp.
Độ phức tạp: \(O(L \log L + q \log L) \) bao gồm chi phí tính mảng \(f\) và tính các truy vấn, không tính chi phí tính \(f[0][x]\).
Code mẫu tham khảo: